#include<iostream>
#include<vector>
using namespace std;

class Node {
public:
	int val;
	Node* left;
	Node* right;
	Node* next;
	Node() : val(0), left(NULL), right(NULL), next(NULL) {}
	Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
	Node(int _val, Node* _left, Node* _right, Node* _next)
		: val(_val), left(_left), right(_right), next(_next) {}
};


class Solution {
public: 
	Node* connect(Node* root) {
		if (!root) return NULL;
		vector<Node*> list;
		list.push_back(root);
		for (int i = 0; i < list.size(); i++) {
			Node* p = list[i];
			if (!p->left) break;
			list.push_back(p->left);
			list.push_back(p->right);
		}
		int start = 1,cap=list.size();
		while (start < cap) {
			int level = start;
			while (level < start * 2) {
				list[level]->next = list[level + 1];
				if (level * 2 + 1 < cap)
					list[level * 2 + 2]->next = list[(level + 1) * 2 + 1];
				level++;
			}
			start = start * 2 + 1;
		}
		return root;
	}
};

void main() {
	Node root(1), l1(2), l2(3), l3(4), l4(5), l5(6), l6(7);
	root.left = &l1, root.right = &l2, l1.left = &l3, l1.right = &l4, l2.left = &l5, l2.right = &l6;
	Solution s;
	s.connect(&root);
}